//303 前缀和与积分图
/*
一维的前缀和，二维的积分图，都是把每个位置之前的一维线段或二维矩形预先存储，方便加速计算
如果需要对前缀和或积分图的值做寻址，则要存在哈希表里；
如果要对每个位置记录前缀和或积分图的值，则可以储存到一维或二维数组里，也常常伴随着动态规划

*/
//Range Sum Query - Immutable
/*
设计一个数据结构，使得其能够快速查询给定数组中，任意两个位置间所有数字的和

输入输出样例
	以下是数据结构的调用样例
vector<int> nums{-2,0,3,-5,2,-1};
NumArray num_array = new NumArray(nums);
num_array.sumRange(0,2); // Result = -2+0+3 = 1.
num_array.sunRange(1,5); // Result = 0+3-5+2-1 = -1.

*/
class NumArray {
	vector<int> psum;
public:
	NumArray(vector<int> nums) : psum(nums.size() + 1, 0) {
		partial_sum(nums.begin(), nums.end(), psum.begin() + 1);
	}
	int sumRange(int i, int j) {
		return psum[j + 1] - psum[i];
	}
};